package com.hqq.leetcode.dp;

/**
 * BackPackIII 背包问题3
 * Description:
 * Given n kind of items with size Ai and value Vi( each item has an infinite number available)
 * and a backpack with size m.
 * What's the maximum value can you put into the backpack?
 * Input:
 * 10,[2,3,5,7],[1,5,2,4]
 * Output:
 * 15
 * <p>
 * Created by heqianqian on 2017/9/17.
 */
public class BackPackIII {

    public static void main(String[] args) {
        int[] A = new int[]{2, 3, 5, 7};
        int[] V = new int[]{1, 5, 2, 4};
        BackPackIII backPack3 = new BackPackIII();
        int max = backPack3.backPackIII(10, A, V);
        System.out.println(max);
    }

    /*
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @param V: Given n items with value V[i]
     * @return: The maximum value
     */
    public int backPackIII(int m, int[] A, int[] V) {
        // write your code here
        int[] dp = new int[m + 1];
        for (int i = 0; i < A.length; i++) {
            for (int j = 1; j <= m; j++) {
                if (j >= A[i]) {
                    dp[j] = Math.max(dp[j], dp[j - A[i]] + V[i]);
                }
            }
        }
        return dp[m];
    }
}
